A number of prior art programming language systems, such as the C++ system, the Ada system, the Modula-3 system, the Smalltalk system, etc., support the aforementioned notion of typed data. As indicated hereinbefore, a data type consists of a representation and a set of functions which can be applied to instances of the data type.
Functions may be thought of as parameterized program fragments which can be invoked (or called) from multiple points in a program. An important consideration in such systems is the correct matching between the declared types of program variables and the types of values assigned to them. Also, the types of the arguments of a function invocation and the argument types expected by the function body which is invoked must be compatible. Incorrect matches between the actual and formal parameters of a function invocation or between variables and their values can lead to unpredictable and incorrect program behavior.
In order to improve program reliability, the type correctness of function invocations and variable assignments can be checked by the programming language system during program preparation (compile-time) or during program execution (runtime). Compile-time type checking is preferred since it can prevent type errors from occurring after the program has been deployed. Additionally, type errors on function invocations or variable assignments are usually indicative of a programming error.
Given a programming language supporting typed data, it is useful to be able to "overload" function names. Function "overloading" allows multiple function instances (or bodies) to be denoted by the same function name. For example, in a programming language having shape types, for example, "circle", "triangle", "rectangle", etc., a function "area" can be defined for each of the shape types. Together, these "area" function instances constitute an overloaded function. The same function name ("area") describes multiple function instances (e.g., area (circle), area (triangle), area (rectangle), etc.) which result in the generation of different code strings and execution sequences at compile and runtimes, respectively.
Processing of invocations of overloaded functions must take into account the number and types of the function arguments at the point of invocation and the number and types of the formal arguments of each instance of the overloaded function to select the proper function instance to be executed.
Recent developments in programming technology, such as the aforementioned C++ systems, the CommonLoops, CLOS system, etc., have extended the semantics,of data types to allow one type to be a subtype of one or more preexisting types (also referred to herein as systems that support multiparent subtypes). In addition, instances of a subtype may be substituted or used in contexts declared to use a supertype of the subtype. This means that an instance of a subtype may be assigned to a variable declared to be one of its supertypes, or passed as an actual parameter to a function whose corresponding formal parameter is declared to be one of its supertypes.
In the foregoing example related to the function "area", a new shape "square" illustrates a subtype of the previously existing data type "rectangle". An instance of a square may be substituted or used in contexts declared to use the supertype rectangle in programming language systems which support subtypes (inheritance) and subtype substitutability.
It is well understood by those skilled in the art that substitutability of subtypes, in conjunction with function overloading, implies that a runtime decision among instances of the overloaded function may be required. Runtime selection of the function instance to be executed (also referred to herein as "dynamic dispatch") may consider the type of only one argument or the types of all the actual arguments.
"Selfish" function selection considers the type of only a single, distinguished actual argument at runtime. "Multimethod" function selection considers the types of all actual arguments to select the function instance that most closely matches the actual argument types of the function call.
Existing examples of programming languages which support compile-time type checking, subtypes, function overloading and dynamic dispatch, such as the Trellis/Owl system, C++, etc., are "selfish", i.e., discriminate on only one of the function arguments (at runtime) to choose between instances of an overloaded function. This means that functional behavior for overloaded functions can be conditioned on only one of the function arguments. Thus, for example, if "integer" is a subtype of "float", such systems cannot directly support overloading of a function such as "MAX" with instances MAX.sub.1 (integer,integer), MAX.sub.2 (float,float), MAX.sub.3 (integer,float) and MAX.sub.4 (float,integer).
Accordingly, it would be desirable to provide a mechanism (and the invention described herein is such a mechanism) which efficiently supports subtyping (with multiple parent types), function overloading, compile-time type checking, and dynamic dispatch based on utilizing the types of all of the actual arguments (to select the proper function instance to execute).
Such a mechanism should guarantee that (1) every function receives arguments which are subtypes of its formal argument types; (2) at least one applicable function instance exists for every function invocation; (3) the actual result type of any method (function) invocation will be consistent with the context of the invocation; and (4) the set of function instances that might be invoked due to subtype substitutions for actual arguments is identified.
Before proceeding to summarize and then set forth the details regarding the methods and apparatus contemplated by the invention, the terms of art used herein, although well known to those skilled in the art, will be defined for the sake of completeness and clarity. Each of these terms (in quotes) is defined as follows:
"Subtype": If type B is a subtype of type A, then every instance of B is also an instance of A. The subtype relationship "B is a subtype of A" is denoted by B.ltoreq.A. If B.ltoreq.A and A.noteq.B, then B is a proper subtype of A (denoted B&lt;A). The subtype relationship is transitive; i.e., B.ltoreq.A C.ltoreq.B=&gt;C.ltoreq.A. If a subtype is a subtype of more than one type, then that subtype is said to have "multiple inheritance".
"Substitutability": If B.ltoreq.A, then an instance of B may be used wherever an instance of A may be used. B is substitutable for A because every instance of B is also an instance of A. In particular, if B.ltoreq.A, then an instance of B may be assigned to a variable declared to be of type A, and instances of B may be passed as arguments of functions whose formal arguments are of type A.
"Function Instance": An executable function instance consists of a function name, a sequence of typed, formal arguments, a result type, and a code body. Function instances are executed with values, specified in the invocation, bound to the arguments. A function instance is denoted by f.sub.k (T.sub.k.sup.1,T.sub.k.sup.2, . . . ,T.sub.k.sup.n).fwdarw.R.sub.k, where f.sub.k is the k-th instance of the function named f, T.sup.j is the formal type of the j-th argument, and R.sub.k is the formal result type.
"Function Arity": The number of arguments of a function.
"Overloaded Function": The set of function instances having the same function name and arity.
"Function Invocation": A call to a function embedded in a program. A function invocation is denoted by f(T.sup.1,T.sup.2, . . . , T.sup.n where "f" is the function name T.sup.i, which is the static type of the i-th argument; i.e., the argument in the i the positive.
"Function Invocation Execution": The performance of a function invocation at runtime. The actual argument types are used, as needed, to select the most specific applicable function instance.
"Formal Argument Type": The type of an argument declared for a function instance.
"Static Argument Type": The declared (or inferred) type of an argument of a function invocation. Static types are determined during compilation using the declared types of variables specified as function invocation arguments or by analysis of expressions specified as function invocation arguments. The static argument type must be a subtype of the formal argument type.
"Actual Argument Type": The type of the argument instance actually bound to a function argument during execution of a function invocation. The actual argument type may differ from one execution of a function invocation to another execution of the same function invocation. The actual argument type must be a subtype of the static argument type.
"Applicable Function Instance": An instance of a function is applicable to a function invocation (or execution of a function invocation) if the function names and arity match, and the static (or actual) type of each argument is a subtype of the corresponding formal argument type. More formally, the function instance f.sub.k (T.sub.k.sup.1,T.sub.k.sup.2, . . . ,T.sub.k.sup.n) is applicable to function invocation f(T.sup.1,T.sup.2, . . . ,T.sup.n) if and only if for every i, 1.ltoreq.i.ltoreq.n, T.sup.i .ltoreq.T.sub.k.sup.i.
"Consistent with Invocation Context": A function invocation is consistent with the invocation context if (1) there is at least one applicable function instance for its static argument type, and (2) if a function instance can be selected for execution at runtime due to the occurrence of instances of subtypes of any of the static argument types, then, (a) if the result of the function invocation is assigned to a variable, the result type of the function invocation is a subtype of that variable; or (b) if the result of the function invocation passes arguments to an enclosing function invocation, then conditions (1) and (2) both hold for the enclosing invocation.
"Function Instance Confusability": Two function instances are confusable if they are both applicable to some function invocation. Formally, function instances f.sub.1 (T.sub.1.sup.1,T.sub.1.sup.2, . . . ,T.sub.1.sup.n) and f.sub.2 (T.sub.2.sup.1,T.sub.2.sup.2, . . . ,T.sub.2.sup.n) are confusable if for every i, 1.ltoreq.i.ltoreq.n, there exists a type T.sup.i, such that T.sup.i .ltoreq.T.sub.1.sup.i T.sup.i T.sub.2.sup.i. Thus, two functions are confusable if there exists a common subtype of the formal argument types at each argument position.
"Confusable Set": A confusable set of methods (function instances) is a maximal set C such that methods m.sub.i and m.sub.j are in C if there are k methods (k could be 0) m.sub.1,m.sub.2, . . . ,m.sub.k such that m.sub.i is confusable with m.sub.1, m.sub.1 is confusable with m.sub.2, . . . , and m.sub.k is confusable with m.sub.j. If a method is not confusable with any other method, it forms a singleton confusable set. Confusable sets over a set of methods M disjointly partition M. It should be noted that confusability is not transitive.
"Static Type Checking": Checking during program compilation that there exists an applicable function instance for every function invocation and that the result type of every potentially applicable function instance is consistent with invocation context.
"Function Instance Specificity": In order to choose between function instances applicable to a function invocation (or execution of a function invocation), a precedence relationship between confusable function instances is needed to select the function instance that most closely matches the function invocation (or execution of the function invocation). If one function instance has precedence over another, then it is more specific. Several examples of function instance precedence rules will be presented. This invention requires a function precedence rule to order confusable function instances, but it does not depend on which precedence rule is used. Examples include:
(1) "Argument Subtype Precedence": If f.sub.1 (T.sub.1.sup.1,T.sub.1.sup.2, . . . ,T.sub.1.sup.n).fwdarw.R.sub.1 and f.sub.2 (T.sub.2.sup.1,T.sub.2.sup.2, . . . ,T.sub.2.sup.n).fwdarw.R.sub.2 are confusable, f.sub.1 has argument subtype precedence (and is more specific than f.sub.2) if for every i, 1.ltoreq.i.ltoreq.n, T.sub.1.sup.i .ltoreq.T.sub.2.sup.i and there exist some j, 1.ltoreq.j.ltoreq.n, such that T.sub.1.sup.j .noteq.T.sub.2.sup.j. Note that argument subtype precedence is sufficient to disambiguate all function invocations in systems which support single inheritance and selfish function selection. However, argument subtype precedence is not sufficient to order all confusable function instances in a system with single inheritance and multimethod function selection.
(2) "Argument Order Precedence": If f.sub.1 (T.sub.1.sup.1,T.sub.1.sup.2, . . . ,T.sub.1.sup.n).fwdarw.R.sub.1 and f.sub.2 (T.sub.2.sup.1,T.sub.2.sup.2, . . . ,T.sub.2.sup.n).fwdarw.R.sub.2 are confusable, f.sub.1 has argument order precedence (and is more specific than f.sub.2) if there exists some first argument position k, 1.ltoreq.k.ltoreq.n, such that T.sub.1.sup.k &lt;T.sub.2.sup.k, and for every m, 1.ltoreq.m&lt;k, T.sub.1.sup.m=T.sub.2.sup.m. It should be noted that the order of argument significance can be any permutation of the argument order. However, it must be uniform for all the function instances of a confusable set. Furthermore, it should be noted that argument order precedence is sufficient to disambiguate all function invocations in systems with single inheritance and multimethod dispatch. For example, consider a system in which types B&lt;A and D&lt;C, and function instances f.sub.1 (A,D) and f.sub.2 (B,C). The functions f.sub.1 and f.sub.2 do not have argument subtype precedence, but they do have argument order precedence with f.sub.2 preceding f.sub.1.
(3) "Global Type Precedence": A partial order over types is established such that subtypes precede their supertypes and any two types T.sub.1, T.sub.2 such that T.sub.1 .notlessthan.T.sub.2 and T.sub.2 .notlessthan.T.sub.1 that have a common subtype are ordered by user directive. More precisely, if A&lt;B, then Index(A)&lt;Index(B) and if C&lt;D C&lt;E, then Index(D)&lt;Index(E) Index(E)&lt;Index(D). If f.sub.1 (T.sub.2.sup.1,T.sub.1.sup.2, . . . ,T.sub.1.sup.n).fwdarw.R.sub.1 and f.sub.2 (T.sub.2.sup.1,T.sub.2.sup.2, . . . ,T.sub.1.sup.n).fwdarw.R.sub.2 are confusable, f.sub.1 has global type precedence (and is more specific than f.sub.2) if there exists some first argument position k, 1.ltoreq.k.ltoreq.n, such that Index(T.sub.1.sup.k)&lt;Index(T.sub.1.sup.k), and for every m, 1.ltoreq.m.ltoreq.k, T.sub.1.sup.m =T.sub.2.sup.m. Note that global-type precedence is sufficient to disambiguate all function invocations in systems with multiple inheritance and multimethod dispatch. For example, consider a system with types C.ltoreq.A and C.ltoreq.B, and A is (user) specified to precede B. Given function instances f.sub.1 (C,A) and f.sub.2 (C,B), f.sub.1 precedes f.sub.2 due to global-type precedence because A precedes B in the global-type ordering.
It should be noted that users must define the ordering between inherited (parent) types when a subtype is defined. The ordering must be consistent with any previously established orderings.
(4) "Inheritance Order Precedence": Let f.sub.1 (T.sub.1.sup.1, T.sub.1.sup.2, . . . ,T.sub.1.sup.n).fwdarw.R.sub.1 and f.sub.2 (T.sub.2.sup.1,T.sub.2.sup.2, . . . ,T.sub.2.sup.n).fwdarw.R.sub.2 be function instances applicable to the function invocation f(T.sup.1,T.sup.2, . . . ,T.sup.n).fwdarw.R. Furthermore, assume that f.sub.1 and f.sub.2 are not ordered by argument subtype or argument order precedence. Then, let there be a first argument position k, such that T.sub.1.sup.k .notlessthan.T.sub.2.sup.k and T.sub.2.sup.k .notlessthan.T.sub.1.sup.k . However both f.sub.1 and f.sub.2 are applicable to function invocation f because T.sup.k .ltoreq.T.sub.1.sup.k and T.sup.k .ltoreq.T.sub.2.sup.k. This can occur when T.sup.k (or some ancestor type) multiply inherits from T.sub.1.sup.k and T.sub.2.sup.k. Inheritance order precedence orders the supertypes of a type such that for every pair of supertypes, T.sub.a and T.sub.b of a type T, T.sub.a &lt;T.sub.b or T.sub.b &lt;T.sub.a with respect to type T. This order can be specified by the user when type T is created, or the order can be inferred from the lexical order of immediate supertypes given in the specification of type T. (Note that specification of a type with an inheritance order incompatible with the inheritance order of the inherited types must be disallowed.) Inheritance order precedence can be defined as follows: f.sub.1 has inheritance order precedence over f.sub.2 with respect to invocation f at argument position k if T.sub.1.sup.k &lt;T.sub.2.sup.k with respect to type T.sup.k. For example, consider the types C&lt;A, C&lt;B, D&lt;A, and D&lt;B. Also, let the inheritance order be A&lt;B with respect to type C and B&lt;A with respect to type D. Now, the function instances f.sub.1 (A) and f.sub.2 (B) are both applicable to a function invocation f(C). Note that f.sub.1 and f.sub.2 have neither argument subtype precedence, nor argument order precedence. However, f.sub.1 has inheritance order precedence for the invocation f(c) because type C inherits from type A before it inherits from type B.
"Most Specific Applicable Function Instance": Given a precedence order among the function instances applicable to a function invocation (or execution of a function invocation), the most specific applicable function instance is the function instance having highest precedence. The most specific applicable function instance of a (static) function invocation is the least specific applicable function that may be executed by that invocation. This follows from the fact that the actual argument types of function invocation must be subtypes of the static argument types.
"Potentially Applicable Function Instance": A function instance is potentially applicable to a function invocation if it is the most specific applicable function instance or is more specific than the most specific applicable function instance and is confusable with the function invocation.
"Function Instance Consistency": Two function instances are consistent if they are not confusable. Otherwise, if f.sub.1 (T.sub.1.sup.1,T.sub.1.sup.2, . . . ,T.sub.1.sup.n).fwdarw.R.sub.1 and f.sub.2 (T.sub.2.sup.1,T.sub.2.sup.2 ; . . . ,T.sub.2.sup.n).fwdarw.R.sub.2 are confusable, they are consistent if: there exists k such that T.sub.1.sup.k .noteq.T.sub.2.sup.k, and if.sub.1 has precedence over f.sub.2 then .sub.1 .ltoreq.R.sub.2, and if f.sub.2 has precedence over f.sub.1 then R.sub.2 .ltoreq.R.sub.1. It should be noted that in the case of Inheritance Order Precedence, f.sub.1 may be both more and less specific than f.sub.2 and therefore the result types R.sub.1 and R.sub.2 must be the same.
Having rigorously defined the terms of art used herein, the invention may now be described with reference to these terms. First, however, it should be recognized that several concepts related to the invention are described or alluded to in recent publications, although no one reference or combination of references is known which describes any one mechanism or set of mechanisms which have the desirable characteristics as outlined hereinbefore.
In particular, an article by Lecluse and Richard entitled "Manipulation of Structured Values in Object-oriented Databases", appearing in the Proceedings of the Second International Workshop On Database Programming Languages (published in 1989), alludes to multimethod dispatch; however, no specific mechanism or procedure is set forth for checking that an applicable method exists. Also missing from this reference is the recognition that procedures and data structures for separating the methods of overloaded functions into confusable sets is, as will be demonstrated hereinafter, a key to solving the problem of being able to provide mechanisms and procedures of the type contemplated by the invention.
An article by P. Dussud, entitled "TICLOS: An Implementation of CLOS for the Explorer Family", OOPSLA (1989), as well as an article by Kiczales and Rodriguez, entitled "Efficient Method Dispatch in PCL", presented at the Conference on Lisp and Functional Programming (1990), describe procedures for dispatching multimethod generic functions. However these articles do not discuss compile-time type checking or the novel application of the concepts of confusability and potentially applicable methods which are demonstrated hereinafter to be utilized in realizing the methods contemplated by the invention.
Most recently, Mugridge, Hammer, and Hosking, in an article entitled "Multi-methods in a Statically-Typed Programming Language", Report No. 50, published by the Department of Computer Science, University of Auckland (1991), although describing the notion of "Potentially Applicable Functions" under the rubric "relevant variants", and the notion of a runtime dispatch for the "relevant variants", fails to describe procedures for identifying the confusable set of a function invocation and fails to teach or even suggest how to obtain and exploit a total ordering of confusable methods (i.e., method precedence rules). Again, the use of confusable sets, a total ordering of confusable methods, etc., will be demonstrated as part of the solution, in accordance with the teachings of the invention, to achieve the aforementioned desirable mechanisms and procedures which support multimethod function overloading with compile-time type checking.